package com.sx.sx1.lintcode.day717;

public class LC219 {


    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }


    static class Solution {
        /**
         * @param head: The head of linked list.
         * @param val:  An integer.
         * @return: The head of new linked list.
         */
        public ListNode insertNode(ListNode head, int val) {
            ListNode ans = new ListNode(-1);
            ListNode tail = ans;
            ListNode node = new ListNode(val);
            boolean add = false;
            if(head ==null){
                return node;
            }
            if(head.val> val){
                node.next=head;
                tail.next=node;
                return ans.next;
            }


            while (head != null) {
                ListNode next = head.next;
                if (!add && next != null && next.val > val) {
                    head.next =null;
                    head.next= node;
                    tail = node;
                    node.next = next;

                    add=true;
                }else{
                    tail.next = head;
                    tail = head;
                }

                head = next;
            }

            if (!add) {
                tail.next = node;
            }
            return ans.next;
        }
    }


    public static void show(ListNode node){
        ListNode cur = node;
        int idx =0;
        while (cur!=null){
            System.out.print(cur.val+" ");
            cur =cur.next;

            if(idx++ > 8) break;
        }

        System.out.println();
    }


    public static void main(String[] args) {
        ListNode root1 = new ListNode(1);
        root1.next = new ListNode(4);
        root1.next.next = new ListNode(6);
        root1.next.next.next = new ListNode(8);

        show(new Solution().insertNode(root1,5));
    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
您有189条未读消息，请及时查看
219 · 在排序链表中插入一个节点
算法
简单
通过率
37%

题目
题解45
笔记
讨论99+
排名
记录
描述
在链表中插入一个节点。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


样例
样例 1：

输入：head = 1->4->6->8->null, val = 5
输出：1->4->5->6->8->null
样例 2：

输入：head = 1->null, val = 2
输出：1->2->null
标签
相关题目

85
在二叉查找树中插入节点
简单

225
在链表中找节点
入门
推荐课程

Twitter 后端系统 - Python 项目实战
从0项目经验到深度后端项目操盘，FB架构师万行代码还原真实开发环境，14周简历镀金
211/1857
已开启智能提示
发起考试
15 分 00 秒
12345678910111213141516171819202122
    }
}
控制台
历史提交

 */